home *** CD-ROM | disk | FTP | other *** search
/ Aminet 6 / Aminet 6 - June 1995.iso / Aminet / gfx / 3d / irit50src.lha / irit5 / cagd_lib / bspboehm.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-23  |  8.4 KB  |  208 lines
  1. /******************************************************************************
  2. * BspBoehm.c - Implements Boehm single knot insertion routine.              *
  3. * Based on:                                      *
  4. * "Recursive proof of Boehm's knot insertion technique", by Phillip J Barry   *
  5. * Ronald N Goldman, CAD, Volume 20 number 4 1988, pp 181-182.              *
  6. * The original paper by Boehm W. is also referenced there.              *
  7. *******************************************************************************
  8. * Written by Gershon Elber, Aug. 90.                          *
  9. ******************************************************************************/
  10.  
  11. #include <ctype.h>
  12. #include <stdio.h>
  13. #include <string.h>
  14. #include "cagd_loc.h"
  15.  
  16. /*****************************************************************************
  17. * DESCRIPTION:                                                               M
  18. * Returns a new curve refined at t (t is inserted as a new knot in Crv).     M
  19. *   If however the multiplicity of t in the current knot vector is equal     M
  20. * (or greater!?) to the degree or t is not in the curve's parametric domain, M
  21. * no new knot is insert and NULL is returned instead.                 M
  22. *   Control mesh is updated as follows (P is old ctl polygon, Q is new):     M
  23. *   Let Index be the last knot in old knot vector less than t and         M
  24. * let j be j = Index - order + 1. Also let k be the curve order. Then,         M
  25. *                                         M
  26. *  Case 1: Q(i) = P(i), i <= j                             V
  27. *                                         V
  28. *          t     -    t(i)        t(i+k-1)  -   t             V
  29. *  case 2: Q(i) = --------------- P(i) + --------------- P(i-1), j<i<=Index  V
  30. *          t(i+k-1) - t(i)        t(i+k-1) - t(i)             V
  31. *                                         V
  32. *  case 3: Q(i) = P(i-1), Index < i                         V
  33. *                                         M
  34. *  Note: Altough works, this is not the optimal way to insert many knot!     M
  35. *  See also the BspKnotEvalAlpha set of routines.                 M
  36. *                                         M
  37. * For more see:                                                              M
  38. * "Recursive proof of Boehm's knot insertion technique", by Phillip J Barry  M
  39. * Ronald N Goldman, CAD, Volume 20 number 4 1988, pp 181-182.             M
  40. * Which also references the original 1980 paper by Boehm.                    M
  41. *                                                                            *
  42. * PARAMETERS:                                                                M
  43. *   Crv:      To refine by adding a new knot with value equal to t. If Crv   M
  44. *             is a periodic curve, it is first unwrapped to a float end      M
  45. *             condition curve.                                               M
  46. *   t:        New knot to insert into Crv.                                   M
  47. *                                                                            *
  48. * RETURN VALUE:                                                              M
  49. *   CagdCrvStruct *:  The refined curve.                                     M
  50. *                                                                            *
  51. * KEYWORDS:                                                                  M
  52. *   BspCrvKnotInsert, refinement, knot insertion                             M
  53. *****************************************************************************/
  54. CagdCrvStruct *BspCrvKnotInsert(CagdCrvStruct *Crv, CagdRType t)
  55. {
  56.     CagdBType
  57.     NewCrv = FALSE,
  58.     IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv);
  59.     CagdRType *KnotVector;
  60.     int i, j, Len, KVLen, Index,
  61.     k = Crv -> Order,
  62.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  63.     CagdCrvStruct *RefinedCrv;
  64.     CagdRType **Points,    **NewPoints;
  65.     
  66.     if (CAGD_IS_PERIODIC_CRV(Crv)) {
  67.     NewCrv = TRUE;
  68.     Crv = CnvrtPeriodic2FloatCrv(Crv);
  69.     }
  70.  
  71.     KnotVector = Crv -> KnotVector;
  72.     Len = Crv -> Length;
  73.     KVLen = k + Len;
  74.     Index = BspKnotLastIndexL(KnotVector, KVLen, t);
  75.     RefinedCrv = CagdCrvNew(Crv -> GType, Crv -> PType, Len + 1);
  76.     Points = Crv -> Points;
  77.     NewPoints = RefinedCrv -> Points;
  78.  
  79.     if (!BspKnotParamInDomain(KnotVector, Len, k, FALSE, t))
  80.     CAGD_FATAL_ERROR(CAGD_ERR_T_NOT_IN_CRV);
  81.  
  82.     /* Update the rest of the RefinedCrv data structure (easy part). */
  83.     RefinedCrv -> Order = k;
  84.     RefinedCrv -> KnotVector = BspKnotInsertOne(Crv -> KnotVector, k, Len, t);
  85.  
  86.     /* Case 1: Copy all points upto (Index - Order + 1) as is. */
  87.     for (i = IsNotRational; i <= MaxCoord; i++)
  88.     CAGD_GEN_COPY(NewPoints[i], Points[i],
  89.               sizeof(CagdRType) * (Index - k + 2));
  90.  
  91.     /* Case 2: Convex blend of exactly 2 points. */
  92.     for (j = Index - k + 2; j <= Index; j++)
  93.     for (i = IsNotRational; i <= MaxCoord; i++)
  94.         NewPoints[i][j] =
  95.            ((t - KnotVector[j]) * Points[i][j] +
  96.         (KnotVector[j + k - 1] - t) * Points[i][j - 1]) /
  97.                       (KnotVector[j + k - 1] - KnotVector[j]);
  98.  
  99.     /* Case 3: Copy all points upto the end. */
  100.     for (i = IsNotRational; i <= MaxCoord; i++)
  101.     CAGD_GEN_COPY(&NewPoints[i][Index + 1],
  102.               &Points[i][Index],
  103.               sizeof(CagdRType) * (Len - Index));
  104.  
  105.     if (NewCrv)
  106.     CagdCrvFree(Crv);
  107.  
  108.     return RefinedCrv;
  109. }
  110.  
  111. /*****************************************************************************
  112. * DESCRIPTION:                                                               M
  113. * Returns a new surface refined at t (t is inserted as a new knot in Srf)    M
  114. * in parametric directipn Dir. See BspCrvKnotInsert for the mathematical     M
  115. * background of this knot insertion algorithm.                     M
  116. *                                                                            *
  117. * PARAMETERS:                                                                M
  118. *   Srf:      To refine by adding a new knot with value equal to t. If Srf   M
  119. *             is a periodic curve, it is first unwrapped to a float end      M
  120. *             condition curve.                                               M
  121. *   Dir:      Of refinement, either U or V.                                  M
  122. *   t:        New knot to insert into Srf.                                   M
  123. *                                                                            *
  124. * RETURN VALUE:                                                              M
  125. *   CagdSrfStruct *:  The refined surface.                                   M
  126. *                                                                            *
  127. * KEYWORDS:                                                                  M
  128. *   BspSrfKnotInsert, refinement, knot insertion                             M
  129. *****************************************************************************/
  130. CagdSrfStruct *BspSrfKnotInsert(CagdSrfStruct *Srf,
  131.                 CagdSrfDirType Dir,
  132.                 CagdRType t)
  133. {
  134.     CagdBType
  135.     NewSrf = FALSE;
  136.     int Row, Col, ULength, VLength, UOrder, VOrder;
  137.     CagdCrvStruct *Crv, *RefCrv;
  138.     CagdSrfStruct
  139.     *RefSrf = NULL;
  140.  
  141.     if (CAGD_IS_PERIODIC_SRF(Srf)) {
  142.     NewSrf = TRUE;
  143.     Srf = CnvrtPeriodic2FloatSrf(Srf);
  144.     }
  145.     
  146.     ULength = Srf -> ULength;
  147.     VLength = Srf -> VLength;
  148.     UOrder = Srf -> UOrder;
  149.     VOrder = Srf -> VOrder;
  150.  
  151.     switch (Dir) {
  152.     case CAGD_CONST_U_DIR:
  153.         RefSrf = BspSrfNew(ULength + 1, VLength, UOrder, VOrder,
  154.                                   Srf -> PType);
  155.         IritFree((VoidPtr) RefSrf -> UKnotVector);
  156.         IritFree((VoidPtr) RefSrf -> VKnotVector);
  157.         RefSrf -> VKnotVector = BspKnotCopy(Srf -> VKnotVector,
  158.                      Srf -> VLength + Srf -> VOrder);
  159.  
  160.         for (Row = 0; Row < VLength; Row++) {
  161.         Crv = BspSrfCrvFromMesh(Srf, Row, CAGD_CONST_V_DIR);
  162.         RefCrv = BspCrvKnotInsert(Crv, t);
  163.  
  164.         if (Row == 0) {          /* Figure out refined knot vector. */
  165.             RefSrf -> UKnotVector = BspKnotCopy(RefCrv -> KnotVector,
  166.                        RefCrv -> Length + RefCrv -> Order);
  167.         }
  168.  
  169.         CagdCrvToMesh(RefCrv, Row, CAGD_CONST_V_DIR, RefSrf);
  170.  
  171.         CagdCrvFree(Crv);
  172.         CagdCrvFree(RefCrv);
  173.         }
  174.         break;
  175.     case CAGD_CONST_V_DIR:
  176.         RefSrf = BspSrfNew(ULength, VLength + 1, UOrder, VOrder,
  177.                                  Srf -> PType);
  178.         IritFree((VoidPtr) RefSrf -> UKnotVector);
  179.         IritFree((VoidPtr) RefSrf -> VKnotVector);
  180.         RefSrf -> UKnotVector = BspKnotCopy(Srf -> UKnotVector,
  181.                     Srf -> ULength + Srf -> UOrder);
  182.  
  183.         for (Col = 0; Col < ULength; Col++) {
  184.         Crv = BspSrfCrvFromMesh(Srf, Col, CAGD_CONST_U_DIR);
  185.         RefCrv = BspCrvKnotInsert(Crv, t);
  186.  
  187.         if (Col == 0) {          /* Figure out refined knot vector. */
  188.             RefSrf -> VKnotVector = BspKnotCopy(RefCrv -> KnotVector,
  189.                        RefCrv -> Length + RefCrv -> Order);
  190.         }
  191.  
  192.         CagdCrvToMesh(RefCrv, Col, CAGD_CONST_U_DIR, RefSrf);
  193.  
  194.         CagdCrvFree(Crv);
  195.         CagdCrvFree(RefCrv);
  196.         }
  197.         break;
  198.     default:
  199.         CAGD_FATAL_ERROR(CAGD_ERR_DIR_NOT_CONST_UV);
  200.         break;
  201.     }
  202.  
  203.     if (NewSrf)
  204.     CagdSrfFree(Srf);
  205.  
  206.     return RefSrf;
  207. }
  208.